In addition to providing a media for calls (that is exchange of voice data), wireless communications networks are increasingly used to provide a platform for the transmission of data, for example to provide information, video and other packet-based services to users of the network. In a wireless communications network, a base station (or other access point) can support one or more users whose link conditions vary. Moreover, users can come and go as they move through the network. Currently, data is transmitted from a base station to one or more user according to predefined data rates. The data rate and number of time slots which are used to transmit packet-based services is determined by channel conditions. When channel conditions are unfavourable, a lower data rate with more time slots is used to transmit data. A mobile user is constantly monitoring RF signal strength of its link with the base station or other access point. It determines the signal to noise ratio (SNR) and uses that to determine what data rate the link conditions will support. Thus, a mobile user will constantly update the base station with data rate requests based on its signal to noise ratio and expected future channel conditions. In turn, the base station transmits data to one mobile user at any given time (measured in time slots, e.g. 1.67 ms) and transmits that data with full power and at a data rate requested by the mobile user. The base station transmits over the radio link with that particular user in that particular time slot, the link constituting a physical signalling channel defined for example by frequency, coding or a combination of the two.
With multiple users therefore it is necessary for the base station to determine for any particular time slot to which mobile station it will transmit data. A scheduler intelligently allocates time slots to optimise throughput by taking advantage of the ups and downs in channel conditions for the mobile users. In the drive towards higher bandwidth, scheduling algorithms that take into account link quality are being standardised and deployed. A Proportional Fairness (PF) algorithm is used in CDMA (code division multiplexed access) HDR (high data rate) networks.
PF is designed to schedule the node whose link quality is the best when normalised with its average throughput. However, the algorithm does not achieve this goal when the channels to different mobile users are heterogeneous, that is when the rate distributions of the channel conditions for different mobile users follow different types of distributions or when the device is rate limited.
Several improvements have been made to compensate for these shortcomings. A score-based (SB) scheduler has been proposed. However, this scheduler is either sensitive to correlation in the packet rates, or requires to store a large amount of data at the scheduler (namely, an extended history of the rate requests for each node).
PF works as follows: for channels (or mobile nodes) j=1, . . . , N requesting rate rj, PF chooses nodes n such that:
                    n        =                              arg                          j              ⁢                                                          ⁢              ɛ              ⁢                              {                                  1                  ,                  …                  ,                  N                                                      max                    ⁡                      (                                          r                j                                            R                j                                      )                                              Equation        ⁢                                  ⁢        1            
                                                        R              j                        ⁡                          (                              t                +                1                            )                                =                                                    (                                  1                  -                                                  )                            ⁢                                                R                  j                                ⁡                                  (                  t                  )                                                      +                                        ⁢                              1                                  (                                      n                    =                    j                                    )                                            ⁢                              r                                  j                  ⁢                                                                                                                            ⁢                                  ⁢                              and            ⁢                                                  ⁢            0                    <                    <          1                                    Equation        ⁢                                  ⁢        2            
The SB considers its scheduling decision by ranking the rate rj(t) against the W previous values rj(t−1), . . . , rj(t−W), thus yielding an ordering score wjin {1, . . . ,}. It schedules the channel for which:n=argjmaxwj with the appropriate tie breaker.   Equation 3
FIG. 1 illustrates the use of a proportional fairness algorithm according to a simple example. Take two nodes sharing one channel. One node, say node 1, can achieve a rate of 1with probability 0.99 or 100 otherwise. The other node, node 2, always achieves a rate of 2. The numbers represent normalised rates for comparison purposes. In reality, rates are measured in Kbps or Mbps. This is illustrated in FIG. 1, which plots R1 and R2 according to equation 2, with =0.01.
PF will roughly work in the following manner. When the rate of node 1 is 100, then it is chosen. Otherwise node 2 is chosen, as long as the scheduler remembers that node 1 has achieved this rate of 100 (how long the scheduler remembers depends on the parameter of the moving average used to estimate the rate of node 1. In FIG. 1, =0.01). Of course, this prevents node 1 from transmitting most of the time. Because the decision is based on the average, the achieved rates are equal. However, while most of the time the channel for node 1 is good enough for transmission, it is node 2 that is chosen. Further, while node 1 can achieve a rate close to 2, it only achieves a rate close to 1 in this situation, while node 2 does achieve its mean rate 2.
For a given channel, what matters for the decision is whether or not this channel is performing beyond its expectations. Proportional Fairness assesses the performance by dividing the current achievable rate by the mean throughput. However, comparing to the achieved throughput is not reliable in this situation.
The SB scheduler has a similar problem. Consider a different example with two nodes as well. Node 2 can achieve the rate sequence of 1 twenty times in a row then 10 five times in a row. Node 2 can achieve a constant rate 2. If the depth (the number of previous rate requests retrieved in the memory) of the scheduler is 3, then node 1 and 2 roughly get chosen with the same probability except for the first two times node 1 can achieve the rate 10. The mean rate achieved in this case is depicted in FIG. 2. The correlation reduces the effect of the scheduling. We see that node 2 achieves rate 1, node 1 achieves rate close to 1.4, which is about the performance of a round robin system.
From these two simple examples, we can see that the scheduling algorithms performed unevenly with respect to the objective they set to achieve.